package combinationSum39;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {


    //思路：定义一个sum函数，循环list进行求和，传入的list就是每次放入的合格元素。如果与target相同则需要把传入的list放入lists中

    List<List<Integer>> lists = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        dfs(candidates,target,0,new ArrayList<>(),lists);

        return lists;
    }

    private void dfs (int[] candidates, int target, int start, List<Integer> step, List<List<Integer>> res) {

        int sum = sums(step);
        if(sum == target){
            res.add(new ArrayList<>(step));
            return;
        }

        if(sum>target){
            //因为是正整数，如果sum大于target则不可能有元素使得sum变小
            return;
        }

        //此处start的作用是避免重复，通过start来标记一次循环位置
        for (int i = start; i < candidates.length; i++) {
            step.add(candidates[i]);
            dfs(candidates,target,i,step,res);
            //一次查找之后需要清空step
            step.remove(step.size() - 1);
        }

    }


    private int sums(List<Integer> step){
        int sum = 0;
        for (int i = 0; i < step.size(); i++) {
            sum+=step.get(i);
        }
        return sum;
    }


    public static void main(String[] args) {
        CombinationSum combinationSum = new CombinationSum();
        System.out.println(combinationSum.combinationSum(new int[]{2, 3, 6, 7}, 7));
    }

}
